{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize Sum Of Array After K Negations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestSumAfterKNegations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 次取反后最大化的数组和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，按以下方法修改该数组：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择某个下标 <code>i</code>&nbsp;并将 <code>nums[i]</code> 替换为 <code>-nums[i]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>重复这个过程恰好 <code>k</code> 次。可以多次选择同一个下标 <code>i</code> 。</p>\n",
    "\n",
    "<p>以这种方式修改数组后，返回数组 <strong>可能的最大和</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,2,3], k = 1\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>选择下标 1 ，nums 变为 [4,-2,3] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,-1,0,2], k = 3\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,-3,-1,5,-4], k = 2\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-100 &lt;= nums[i] &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-sum-of-array-after-k-negations](https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-sum-of-array-after-k-negations](https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,3]\\n1', '[3,-1,0,2]\\n3', '[2,-3,-1,5,-4]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        i = 0\n",
    "        while i<len(nums) and nums[i]<0 and k>0:\n",
    "            nums[i] = nums[i]*-1\n",
    "            k-=1\n",
    "            i+=1\n",
    "        if k%2==0:\n",
    "            return sum(nums)\n",
    "        else:return sum(nums)-2*min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        while k:\n",
    "            nums.sort()\n",
    "            nums[0] = -nums[0]\n",
    "            k-=1\n",
    "            print(nums)\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:        \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(n):\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                nums[i] = -nums[i]\n",
    "                k -= 1\n",
    "\n",
    "        res = sum(nums)\n",
    "        if k > 0:\n",
    "            if k % 2 != 0:\n",
    "                # nums.sort()\n",
    "                # nums[0] = -nums[0]\n",
    "                min_num = min(nums)\n",
    "                if min_num >= 0:\n",
    "                    res -= 2 * min_num\n",
    "                else:\n",
    "                    res += 2 * min_num\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        idx = 0\n",
    "        for i in range(k):\n",
    "            min_value = float(\"inf\")\n",
    "            for j in range(len(nums)):\n",
    "                if nums[j] < min_value:\n",
    "                    min_value = nums[j]\n",
    "                    idx = j\n",
    "            nums[idx] =-nums[idx]\n",
    "            print(nums)\n",
    "            \n",
    "        return sum(nums)\n",
    "                \n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left = 0 \n",
    "        while left < len(nums) and nums[left] < 0 and k > 0:\n",
    "            nums[left] = -nums[left]\n",
    "            left += 1\n",
    "            k -= 1\n",
    "        nums.sort()\n",
    "        if k % 2 == 1:\n",
    "            nums[0] = -nums[0]\n",
    "        return sum(nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        # rude method\n",
    "        # sort the input list first, then switch the ele from the head until meet the positive ele\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            if k <= 0:\n",
    "                break\n",
    "            else:\n",
    "                nums[i] = -nums[i]\n",
    "                k -= 1\n",
    "                if i < len(nums)-1 and nums[i+1] < nums[i]:\n",
    "                    i += 1\n",
    "            print(nums)\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, AB: List[int], K: int) -> int:\n",
    "        for _ in range(K):\n",
    "            mi = min(AB)\n",
    "            AB.sort(reverse=True)\n",
    "            print(AB)\n",
    "            AB.pop()\n",
    "            AB.append(-mi)\n",
    "        return sum(AB)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        N = len(nums)\n",
    "        n = min(k,N)\n",
    "        times = 0\n",
    "        print(k,N,n)\n",
    "        for i in range(n):\n",
    "            if nums[i] < 0:\n",
    "                nums[i] = - nums[i]\n",
    "                times += 1\n",
    "            else:\n",
    "                break\n",
    "            print(i,nums)\n",
    "\n",
    "        print(i)\n",
    "        if times < k:\n",
    "            nums.sort()\n",
    "            nums[0] = nums[0] * (-1)**(k-times)\n",
    "                \n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        freq = Counter(nums)\n",
    "        ans = sum(nums)\n",
    "        for i in range(-100, 0):\n",
    "            if freq[i]:\n",
    "                ops = min(k, freq[i])\n",
    "                ans += -i * ops * 2\n",
    "                freq[i] -= ops\n",
    "                freq[-i] += ops\n",
    "                k -= ops\n",
    "                if k == 0:\n",
    "                    break\n",
    "        \n",
    "        if k > 0 and k % 2 == 1 and not freq[0]:\n",
    "            for i in range(1, 101):\n",
    "                if freq[i]:\n",
    "                    ans -= i * 2\n",
    "                    break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<0 and k>0:\n",
    "                nums[i]*=-1\n",
    "                k-=1\n",
    "            \n",
    "        if k%2==1:\n",
    "            c=nums.index(min(nums))\n",
    "            nums[c]=-nums[c]\n",
    "\n",
    "\n",
    "        b=sum(nums)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(n):\n",
    "            if nums[i]<0 and k>0:\n",
    "                nums[i] *= -1\n",
    "                k -= 1\n",
    "        nums.sort()\n",
    "        if k%2 == 0:\n",
    "            return sum(nums)\n",
    "        else:\n",
    "            return sum(nums[1:])-nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return sum(nums) - 2 * min(nums)\n",
    "        i = nums.index(min(nums))\n",
    "        nums[i] = -nums[i]\n",
    "        return self.largestSumAfterKNegations(nums, k - 1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n",
    "        A.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组A\n",
    "\n",
    "        for i in range(len(A)):  # 第二步：执行K次取反操作\n",
    "            if A[i] < 0 and K > 0:\n",
    "                A[i] *= -1\n",
    "                K -= 1\n",
    "\n",
    "        if K % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反\n",
    "            A[-1] *= -1\n",
    "\n",
    "        result = sum(A)  # 第四步：计算数组A的元素和\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        j = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if k == 0:\n",
    "                break\n",
    "            if nums[i] < 0:\n",
    "                nums[i] = -nums[i]\n",
    "                k -= 1\n",
    "            else:\n",
    "                break\n",
    "        nums.sort()\n",
    "        nums[0] = nums[0] if k%2 == 0 else -nums[0]\n",
    "\n",
    "        for i,num in enumerate(nums):\n",
    "            res += nums[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted(nums,key=abs,reverse=True)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<0 and k>0:\n",
    "                nums[i] = -nums[i]\n",
    "                k-=1\n",
    "        if k%2!=0:  #num[i]>=0 or k==0,如果是k>0，则是nums[i]>0\n",
    "            nums[-1]=-nums[-1]\n",
    "        return sum(nums)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        nearest = inf\n",
    "        while i<len(nums):\n",
    "            nearest = min(abs(nums[i]), abs(nearest)) \n",
    "            if nums[i]<0 and k > 0:\n",
    "                ans += (-nums[i])\n",
    "                k -= 1\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += nums[i]\n",
    "                i += 1\n",
    "        \n",
    "        if k == 0 or (k > 0 and k %2 == 0):\n",
    "            return ans\n",
    "        else:\n",
    "            return ans - 2 * nearest\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        # 以绝对值进行排序\n",
    "        a = sorted(nums, key=lambda x: abs(x), reverse=True)\n",
    "        # print(a)\n",
    "        for i, x in enumerate(a):\n",
    "            if x < 0 and k > 0:\n",
    "                a[i] *= -1\n",
    "                k -= 1\n",
    "        if k % 2 == 1:\n",
    "            a[-1] *= -1\n",
    "        # print(a)\n",
    "        return sum(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        '''nums.sort(reverse=True)\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                nums[i] *= -1\n",
    "                k -= 1\n",
    "        nums.sort(reverse=True)\n",
    "        if k%2 == 1:\n",
    "            nums[-1] *= -1\n",
    "        sum_num = sum(nums)\n",
    "        return sum_num'''\n",
    "        nums.sort(key=abs, reverse=True)#按绝对值降序排序\n",
    "        for i in range(len(nums)):  # 第二步：执行K次取反操作\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                nums[i] *= -1\n",
    "                k -= 1\n",
    "\n",
    "        if k % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反\n",
    "            nums[-1] *= -1\n",
    "\n",
    "        result = sum(nums)  # 第四步：计算数组A的元素和\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=abs, reverse=True)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                nums[i] *= -1\n",
    "                k -= 1\n",
    "        if k % 2 == 1:\n",
    "            nums[-1] *= -1\n",
    "        return sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(0, len(nums)):\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                k -= 1\n",
    "                nums[i] = -nums[i]\n",
    "            elif nums[i] == 0:\n",
    "                k = 0\n",
    "                break\n",
    "        nums.sort()\n",
    "        if k != 0:\n",
    "            if k % 2 != 0:\n",
    "                nums[0] = -nums[0]\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按绝对值降序排序数组nums\n",
    "\n",
    "        for i in range(len(nums)):  # 第二步：执行K次取反操作\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                nums[i] = -nums[i]\n",
    "                k -= 1\n",
    "\n",
    "        if k % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反\n",
    "            nums[-1] = -nums[-1]\n",
    "\n",
    "        result = sum(nums)  # 第四步：计算数组A的元素和\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        while k>0:\n",
    "            m=min(nums)\n",
    "            if m<0:\n",
    "                nums[nums.index(m)]=-m\n",
    "            else:\n",
    "                break\n",
    "            k-=1\n",
    "        if k>0 and k % 2:\n",
    "            m=min(nums)\n",
    "            nums[nums.index(m)]=-m\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, A: List[int], k: int) -> int:\n",
    "        A.sort(key=lambda x: abs(x), reverse=True)\n",
    "        for i in range(len(A)):\n",
    "            if A[i]<0 and k>0:\n",
    "                A[i]*=-1\n",
    "                k-=1\n",
    "        if k%2==1:\n",
    "            A[-1]*=-1\n",
    "        return sum(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] >= 0 or k == 0:\n",
    "                break\n",
    "            nums[i] = -nums[i]\n",
    "            k -= 1 \n",
    "        \n",
    "        if k > 0:\n",
    "            k = k % 2\n",
    "        \n",
    "        return sum(nums) - k * 2 * min(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=lambda x: abs(x), reverse=True)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if k == 0:\n",
    "                break\n",
    "\n",
    "            if nums[i] < 0:\n",
    "                nums[i] = -nums[i]\n",
    "                k -= 1\n",
    "\n",
    "        if k % 2 == 1:\n",
    "            nums[-1] = -nums[-1]\n",
    "\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=lambda x:abs(x),reverse=True)\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i]<0 and k>0:\n",
    "                k-=1\n",
    "                nums[i]=-nums[i]\n",
    "\n",
    "        if k%2==1:\n",
    "            nums[n-1]=-nums[n-1]\n",
    "        return sum(nums)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort(key = lambda x : abs(x), reverse=True) # 按绝对值从大到小排列\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                k -= 1\n",
    "                nums[i] = -nums[i]\n",
    "        \n",
    "        if k != 0: # k没用完，取绝对值最小的取反,最后一个就行！\n",
    "\n",
    "            nums[-1] = nums[-1] * (-1) ** k\n",
    "\n",
    "        return sum(nums) \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=lambda x: abs(x), reverse=True)\n",
    "        # i = 0\n",
    "        # while k != 0:\n",
    "        #     if i == len(nums):\n",
    "        #         nums[-1] = -nums[-1]\n",
    "        #         k -= 1\n",
    "        #         continue\n",
    "        #     if nums[i] < 0:\n",
    "        #         nums[i] = -nums[i]\n",
    "        #         i += 1\n",
    "        #         k -= 1\n",
    "        #     else:\n",
    "        #         i += 1\n",
    "        # return sum(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if k > 0 and nums[i] < 0:\n",
    "                nums[i] = -nums[i]\n",
    "                k -= 1\n",
    "        if k % 2 == 1:\n",
    "            nums[-1] = -nums[-1]\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        n=len(nums)\n",
    "        while i<n and k>0:\n",
    "            if nums[i]<0:\n",
    "                nums[i]=-nums[i]\n",
    "                k-=1\n",
    "                i+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        if k==0:\n",
    "            return sum(nums)\n",
    "        elif i==n and k>0 and k%2:\n",
    "            return sum(nums)-2*min(nums)\n",
    "        else:\n",
    "            return sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        while i<k:\n",
    "            if i>=len(nums) or nums[i]>=0:\n",
    "                break\n",
    "            nums[i]*=-1\n",
    "            i+=1\n",
    "        \n",
    "        if i>=k:\n",
    "            return sum(nums)\n",
    "        else:\n",
    "            nums.sort()\n",
    "            while i<k:\n",
    "                nums[0]*=-1\n",
    "                i+=1\n",
    "            return sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        # s = sorted(nums)\n",
    "        # i = 0\n",
    "        # while k and i < len(s):\n",
    "        #     if s[i] < 0 and i < len(s) -1:\n",
    "        #         s[i] = -s[i]\n",
    "        #         k -= 1\n",
    "        #         i += 1\n",
    "        #     else:\n",
    "        #         if s[i] > s[i-1] and i > 0:\n",
    "        #             s[i-1] = s[i-1] * (-1) ** k\n",
    "        #         else:\n",
    "        #             s[i] = s[i] * (-1) ** k \n",
    "        #         k = 0 \n",
    "        # return sum(s)\n",
    "        heapq.heapify(nums)\n",
    "        while k > 0:\n",
    "            heapq.heappush(nums, -heapq.heappop(nums))\n",
    "            k -= 1\n",
    "        return sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            if nums[0] < 0:\n",
    "                nums[0] = -nums[0]\n",
    "                nums.sort()\n",
    "            else:\n",
    "                nums[0] = -nums[0]\n",
    "        for i in nums:\n",
    "            ans += i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n",
    "        A.sort(key=lambda x: abs(x), reverse=True)\n",
    "        for i in range(len(A)):\n",
    "            if K <= 0:\n",
    "                break\n",
    "            if A[i] < 0:\n",
    "                A[i] = -A[i]\n",
    "                K -= 1\n",
    "        if K % 2 == 1:\n",
    "            A[-1] = -A[-1]\n",
    "        return sum(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        for i, x in enumerate(nums):\n",
    "            if x >= 0 or k == 0:\n",
    "                break\n",
    "            k -= 1\n",
    "            nums[i] = -nums[i]\n",
    "        if k % 2:\n",
    "            nums.sort()\n",
    "            nums[0] = -nums[0]\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums = sorted(nums)\n",
    "        max_neg = 0\n",
    "        for i in range(len(nums)):\n",
    "            if k == 0:\n",
    "                break\n",
    "            if k > 0 and nums[i] < 0:\n",
    "                max_neg = max(max_neg, nums[i])\n",
    "                k -= 1\n",
    "                nums[i] = -nums[i]\n",
    "            elif nums[i] == 0:\n",
    "                k = 0\n",
    "            elif i > 0 and nums[i] > 0:\n",
    "                if k % 2 == 0:\n",
    "                    k = 0\n",
    "                elif nums[i] <= nums[i-1]:\n",
    "                    nums[i] = -nums[i]\n",
    "                else:\n",
    "                    nums[i-1] = -nums[i-1]\n",
    "                k = 0\n",
    "        if k % 2 == 1:\n",
    "            nums[-1] = -nums[-1]\n",
    "        return sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        for _ in range(k):\n",
    "            Min = min(nums)\n",
    "            nums.append(-Min)\n",
    "            nums.remove(Min)\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        s = sorted(nums)\n",
    "        i = 0\n",
    "        while k and i < len(s):\n",
    "            if s[i] < 0 and i < len(s) -1:\n",
    "                s[i] = -s[i]\n",
    "                k -= 1\n",
    "                i += 1\n",
    "            else:\n",
    "                if s[i] > s[i-1] and i > 0:\n",
    "                    s[i-1] = s[i-1] * (-1) ** k\n",
    "                else:\n",
    "                    s[i] = s[i] * (-1) ** k \n",
    "                k = 0 \n",
    "        return sum(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            if nums[0] < 0:\n",
    "                nums[0] = -nums[0]\n",
    "                nums.sort()\n",
    "            else:\n",
    "                nums[0] = -nums[0]\n",
    "        for i in nums:\n",
    "            ans += i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        minIndex = 0\n",
    "        largeSum = 0\n",
    "        nums = sorted(nums)\n",
    "        for i in range(k):\n",
    "            i = i % len(nums)\n",
    "            if nums[i] < nums[minIndex]:\n",
    "                nums[i] = -nums[i]\n",
    "                minIndex = i\n",
    "            else:\n",
    "                nums[minIndex] = -nums[minIndex]\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=lambda x:abs(x),reverse=True)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<0 and k>0:\n",
    "                nums[i]=-nums[i]\n",
    "                k-=1\n",
    "        if k%2==1:\n",
    "            nums[-1]=-nums[-1]\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        #按照绝对值从大到小进行排序\n",
    "        #在k次操作内将负数改成正数\n",
    "        #如果还没用完k次，则对最后一个最小的数进行变换\n",
    "        #最终返回最大值\n",
    "        nums.sort(key=lambda x: abs(x), reverse=True)\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] < 0 and k:\n",
    "                nums[i] *= -1\n",
    "                k -= 1\n",
    "        if k%2==1:\n",
    "            nums[i] *= -1\n",
    "        return sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key = lambda x:abs(x), reverse = True)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                nums[i] = -nums[i]\n",
    "                k -= 1\n",
    "        if k % 2 == 1:\n",
    "            nums[-1] = -nums[-1]\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if k>0:\n",
    "                num = nums[i]\n",
    "                if num < 0:\n",
    "                    nums[i] = -num\n",
    "                    k-=1\n",
    "                elif num >= 0:\n",
    "                    break\n",
    "        nums.sort()\n",
    "        while k>0:\n",
    "            nums[0] = -nums[0]\n",
    "            k-=1\n",
    "        return sum(nums)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        heapify(nums)\n",
    "        for _ in range(k):\n",
    "            a = heappop(nums)\n",
    "            if a == 0:\n",
    "                break\n",
    "            heappush(nums,-a)\n",
    "        return sum(nums)\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                nums[i] = -nums[i]\n",
    "                k -= 1\n",
    "            else:\n",
    "                break\n",
    "        if k % 2 == 0 :\n",
    "            return sum(nums)\n",
    "        if k % 2 == 1:\n",
    "            return (sum(nums) - 2*min(nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "         nums.sort(key=lambda x: abs(x), reverse=False)  # 第一步：按照绝对值降序排序数组A\n",
    "         result=float('-inf')\n",
    "         for i in range(len(nums)-1,-1,-1):\n",
    "             if nums[i]<0 and k>0:\n",
    "                 nums[i]=-nums[i]\n",
    "                 k-=1\n",
    "         while k>0:\n",
    "            nums[0]=-nums[0]\n",
    "            k-=1\n",
    "         return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        freq = Counter(nums)\n",
    "        ans = sum(nums)\n",
    "        for i in range(-100, 0):\n",
    "            if freq[i]:\n",
    "                ops = min(k, freq[i])\n",
    "                ans += -i * ops * 2\n",
    "                freq[i] -= ops\n",
    "                freq[-i] += ops\n",
    "                k -= ops\n",
    "                if k == 0:\n",
    "                    break\n",
    "        \n",
    "        if k > 0 and k % 2 == 1 and not freq[0]:\n",
    "            for i in range(1, 101):\n",
    "                if freq[i]:\n",
    "                    ans -= i * 2\n",
    "                    break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        # lambda语法糖\n",
    "        nums.sort(key = lambda x: abs(x), reverse=True)\n",
    "        for i in range(len(nums)):\n",
    "            # k > 0条件要注意\n",
    "            if nums[i]<0 and k > 0:\n",
    "                nums[i] *= -1\n",
    "                k -= 1\n",
    "        if k % 2 == 1:\n",
    "            nums[-1] *= -1\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=lambda x: abs(x),reverse = True)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                nums[i] = -nums[i]\n",
    "                k -= 1\n",
    "        if k % 2 == 1:\n",
    "            nums[-1] = -nums[-1]\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        while k>0:\n",
    "            if nums[0]<0 or nums[0]>0:\n",
    "                nums[0] = - nums[0]\n",
    "                k-=1\n",
    "                nums.sort()  # 改变后要重新排序\n",
    "            else:\n",
    "                return sum(nums)\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key = lambda x: abs(x), reverse = True)\n",
    "        result = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] <0 and k >0:\n",
    "                nums[i] *= -1\n",
    "                k -= 1\n",
    "        if k %2 ==1:\n",
    "            nums[len(nums)-1] = nums[len(nums)-1] * -1\n",
    "        for j in range(len(nums)):\n",
    "            result += nums[j]\n",
    "        return result\n",
    "\n",
    "# def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n",
    "#         A.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组A\n",
    "\n",
    "#         for i in range(len(A)):  # 第二步：执行K次取反操作\n",
    "#             if A[i] < 0 and K > 0:\n",
    "#                 A[i] *= -1\n",
    "#                 K -= 1\n",
    "\n",
    "#         if K % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反\n",
    "#             A[-1] *= -1\n",
    "\n",
    "#         result = sum(A)  # 第四步：计算数组A的元素和\n",
    "#         return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if nums[mid]==0:\n",
    "                left=mid\n",
    "                break\n",
    "            if nums[mid]<0:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        print(left,k)\n",
    "        if left>=k:\n",
    "            for i in range(k):\n",
    "                nums[i]=-nums[i]\n",
    "        else:\n",
    "            for i in range(left):\n",
    "                nums[i]=-nums[i]\n",
    "            k-=left\n",
    "            if k%2==1:\n",
    "                if left==len(nums):\n",
    "                    nums[-1]=-nums[-1]\n",
    "                elif left>0 and nums[left-1]<nums[left]:\n",
    "                    nums[left-1]=-nums[left-1]\n",
    "                else:\n",
    "                    nums[left]=-nums[left]\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        for i in range(k):\n",
    "\n",
    "            if i < len(nums) and nums[i] <= 0:\n",
    "                nums[i] = -nums[i]\n",
    "            else:\n",
    "                min_num = min(nums)\n",
    "                min_index = nums.index(min_num)\n",
    "                nums[min_index] = -nums[min_index]\n",
    "\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            num_min = min(nums)\n",
    "            min_index = nums.index(num_min)\n",
    "            nums[min_index] = -num_min\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        while k>0:\n",
    "            a=nums.index(min(nums))\n",
    "            nums[a]=-nums[a]\n",
    "            k-=1\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        while k>0:\n",
    "            if nums[0]<0 or nums[0]>0:\n",
    "                nums[0] = - nums[0]\n",
    "                k-=1\n",
    "                nums.sort()  # 改变后要重新排序\n",
    "            else:\n",
    "                return sum(nums)\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=lambda x: abs(x), reverse=True)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                k -= 1\n",
    "                nums[i] *= -1\n",
    "        \n",
    "        if k % 2 == 1:\n",
    "            nums[-1] *= -1\n",
    "        \n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            nums.sort()\n",
    "            nums[0] = - nums[0]\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        a=sorted(nums)\n",
    "        for i in range(len(a)):\n",
    "            if k>0 and a[i]<0:\n",
    "                a[i]*=-1\n",
    "                k-=1\n",
    "        if k>0:\n",
    "            a=sorted(a)\n",
    "            a[0]*=(-1)**k\n",
    "        return sum(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n",
    "        A.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组A\n",
    "\n",
    "        for i in range(len(A)):  # 第二步：执行K次取反操作\n",
    "            if A[i] < 0 and K > 0:\n",
    "                A[i] *= -1\n",
    "                K -= 1\n",
    "\n",
    "        if K % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反\n",
    "            A[-1] *= -1\n",
    "\n",
    "        result = sum(A)  # 第四步：计算数组A的元素和\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        ind = 0\n",
    "        while k:\n",
    "            nums[ind] = -nums[ind]            \n",
    "            if ind < len(nums)-1 and nums[ind]>nums[ind+1]:\n",
    "                ind += 1\n",
    "            k -= 1\n",
    "        return sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组A\n",
    "        for i in range(len(nums)):  # 第二步：执行K次取反操作\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                nums[i] *= -1\n",
    "                k -= 1\n",
    "\n",
    "        if k % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反\n",
    "            nums[-1] *= -1\n",
    "\n",
    "        result = sum(nums)  # 第四步：计算数组A的元素和\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n",
    "        A.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组A\n",
    "\n",
    "        for i in range(len(A)):  # 第二步：执行K次取反操作\n",
    "            if A[i] < 0 and K > 0:\n",
    "                A[i] *= -1\n",
    "                K -= 1\n",
    "\n",
    "        if K % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反\n",
    "            A[-1] *= -1\n",
    "\n",
    "        result = sum(A)  # 第四步：计算数组A的元素和\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(key=lambda x: abs(x), reverse=True)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0 < k:\n",
    "                nums[i] *= -1\n",
    "                k -= 1\n",
    "        if k % 2 == 1:\n",
    "            nums[-1] *= -1\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        sum_num = sum(nums)\n",
    "        while 1:\n",
    "            if k > 0:\n",
    "                if nums[0] <= 0:\n",
    "                    nums[0] = -nums[0]\n",
    "                    nums.sort()\n",
    "                    sum_num = sum(nums)\n",
    "                else:\n",
    "                    nums[0] = -nums[0]\n",
    "                    sum_num = sum(nums)\n",
    "                k -= 1\n",
    "            else:\n",
    "                break\n",
    "        return sum_num\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        n=len(nums)\n",
    "        while i<n and k>0:\n",
    "            if nums[i]<0:\n",
    "                nums[i]=-nums[i]\n",
    "                k-=1\n",
    "            i+=1\n",
    "        if i==n and k%2:\n",
    "            return sum(nums)-2*min(nums)\n",
    "        else:\n",
    "            return sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums=sorted(nums,key=abs,reverse=True)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<0 and k>0:\n",
    "                k-=1\n",
    "                nums[i]*=-1\n",
    "        # print(nums)\n",
    "        while k>0:\n",
    "            nums[-1]*=-1\n",
    "            k-=1\n",
    "\n",
    "        return sum(nums)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while i < min(k, n) and nums[i] < 0:\n",
    "            cnt -= nums[i]\n",
    "            i += 1\n",
    "        \n",
    "        if i == k:\n",
    "            return cnt + sum(nums[k:])\n",
    "        \n",
    "        if i == n:\n",
    "            return cnt + 2 * nums[-1] * ((k - n) % 2)\n",
    "        \n",
    "        if i == 0:\n",
    "            flag = -2 * nums[i] * ((k - i) % 2)\n",
    "        else:\n",
    "            flag = max(-2 * nums[i] * ((k - i) % 2), 2 * nums[i-1] * ((k - i) % 2))\n",
    "        return cnt + sum(nums[i:]) + flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        # 将数组按绝对值大小从大到小排序\n",
    "        nums.sort(key=lambda x: abs(x), reverse=True)\n",
    "        for i in range(len(nums)):\n",
    "            if k > 0 and nums[i] < 0 :\n",
    "                nums[i] *= -1\n",
    "                k -= 1\n",
    "        # 如果k还有剩余次数，将最小值取反 \n",
    "        # 解释： 如果k还剩奇数次，那么将最小值反转一次， 如果为偶数，反转两次，即为不变\n",
    "        if k % 2 == 1:\n",
    "            nums[-1] *= -1\n",
    "        result = sum(nums)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        freq = Counter(nums)\n",
    "        ans = sum(nums)\n",
    "        for i in range(-100, 0):\n",
    "            if freq[i]:\n",
    "                ops = min(k, freq[i])\n",
    "                ans += -i * ops * 2\n",
    "                freq[i] -= ops\n",
    "                freq[-i] += ops\n",
    "                k -= ops\n",
    "                if k == 0:\n",
    "                    break\n",
    "        \n",
    "        if k > 0 and k % 2 == 1 and not freq[0]:\n",
    "            for i in range(1, 101):\n",
    "                if freq[i]:\n",
    "                    ans -= i * 2\n",
    "                    break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums = sorted(nums)\n",
    "        min_idx = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0 and k>0:\n",
    "                nums[i] = -nums[i]\n",
    "                k -= 1\n",
    "            if nums[i] < nums[min_idx]:\n",
    "                min_idx = i\n",
    "\n",
    "        print(nums[min_idx])\n",
    "        while k>0:\n",
    "            nums[min_idx] = - nums[min_idx]\n",
    "            k -= 1\n",
    "        return sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组A\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0 and k > 0:\n",
    "                nums[i] *= -1\n",
    "                k -=1\n",
    "\n",
    "        if k % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反\n",
    "            nums[-1] *= -1\n",
    "\n",
    "        result = sum(nums)  # 第四步：计算数组A的元素和\n",
    "        return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while i < min(k, n) and nums[i] < 0:\n",
    "            cnt -= nums[i]\n",
    "            i += 1\n",
    "        \n",
    "        if i == k:\n",
    "            return cnt + sum(nums[k:])\n",
    "        \n",
    "        if i == n:\n",
    "            return cnt + 2 * nums[-1] * ((k - n) % 2)\n",
    "        \n",
    "        if i == 0:\n",
    "            flag = -2 * nums[i] * ((k - i) % 2)\n",
    "        else:\n",
    "            flag = max(-2 * nums[i] * ((k - i) % 2), 2 * nums[i-1] * ((k - i) % 2))\n",
    "        return cnt + sum(nums[i:]) + flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:\n",
    "        from copy import deepcopy\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        final_nums = deepcopy(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]<0 and k>0:\n",
    "                k-=1\n",
    "                final_nums[i] = nums[i]*(-1)\n",
    "        final_nums.sort()\n",
    "        if k %2 ==1:\n",
    "            final_nums[0] =final_nums[0]*(-1)\n",
    "        # print(sum(final_nums))\n",
    "        return sum(final_nums)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
